\section{Metaheurística Tabú Search}

\subsection{Introducción}
En esta sección explicaremos cómo fue que resolvimos el problema mediante la técnica metaheurística \textbf{Tabú}, una técnica en la cuál se incluyen temas vistos en el algoritmo constructivo y además en la búsqueda local, pero en este caso tratando de no quedarse estancado en los mínimos locales, como haría la búsqueda local, y tratar de buscar la solución por caminos que al principio no parecerían tener sentido.

\subsection{Desarrollo}
En este algoritmo heredamos la idea de vecindad explicada en la sección de la búsqueda local: establecemos la vecindad entre dos soluciones cuando difieren en exactamente dos ejes. Además, seguimos con la misma política de no analizar mover nodos del circuito si éste tiene 4 elementos.

Nuestro algoritmo, básicamente, sigue el siguiente procedimiento:
\begin{compactenum}
 \item Recibimos una instancia inicial (que podría ser la de la constructiva).
 \item Mientras no se cumpla el criterio de parada
  \begin{compactenum}[1.]
    \item De todos los movimientos posibles dentro de la vecindad (ya explicado en búsqueda local) nos quedamos con el mejor siempre y cuando realizar el movimiento no sea tabú.
  	\item Si esa nueva solución me mejora lo que tenía, actualizo y sigo iterando.
  	\item Sino, agrego el movimiento a la lista tabú y sigo iterando.
%    \item elegir un nodo tal que no esté en la lista tabú
%    \item elegir otros dos nodos tal que pongo a este nodo entre ellos en el circuito al que pertenezcan ellos
%    \item guardarse la solución, compararla con la mejor hasta el momento y agregar los tres nodos a la lista tabú como una terna. Si ésta está llena, eliminar la primer terna de la lista (la más vieja).
  \end{compactenum}
\end{compactenum}

En cuanto al criterio de parada, decidimos realizar una cantidad fija de iteraciones. Intentamos pensar algo más interesante que eso como que si después de \textit{x} iteraciones (\textit{x} constante) la solución no se mejora termino, pero el cómo encontrar una buena aproximación/cota para ese valor resultaba muy difícil.

En cuanto a la lista tabú, lo ideal hubiera sido guardarse ambos circuitos completos pero como esto es muy costoso hay que guardar ciertas características del movimiento que sirvan para que no ése no se vuelva a realizar pero sí otros movimientos ``similares'' a él. De cualquier manera, esto no siempre es posible ya que esas características nunca van a poder representar completamente al estado en que estaban los circuitos. Aún así, nosotros decidimos guardarnos el nodo que se mueve, entre quiénes y los tamaños que tenían los circuitos, y nos dió buenos resultados.

En cuanto al tamaño de la lista, éste tiene que ser acotado también. Por un lado por el mismo motivo que en las iteraciones: la memoria. Pero también existe otro problema un tanto particular que es que si yo pongo una lista, digamos, infinita, van a haber movimientos que van a estar prohibidos para siempre (y que si la lista no fuera infinita, eventualmente dejarían de ser tabú) y, como ya dijimos, cuando prohibimos un movimiento no sólo estamos prohibiendo ese sino también movimientos similares que compartan las características. Luego podría nunca llegar a una solución porque hay un movimiento tabú que nunca dejó de serlo.




\subsection{Pseudocódigo}

\begin{algorithm}[H]
\caption{\operMA{TabuSearch}{ \vin{inst}{InstanceResultado}, \vin{inst\_pesos}{InstanceTP3}, \vin{tabu\_size}{int}, \vin{cant\_iteraciones}{int} }}
%InstanceResultado inst, InstanceTP3 inst_pesos
\begin{algorithmic}[1]\parskip=1mm

%\STATE $s \leftarrow$ solución de la constructiva
\STATE \textit{listatabú} $\leftarrow$ lista vacía
\STATE iteraciones $\leftarrow$ 0

\WHILE {iteraciones $<$ cant\_iteraciones}
	\STATE iteraciones ++ \COMMENT Voy a realizar una iteración más
	\STATE \COMMENT Elegir mejor solución vecina tal que no esté en la lista tabú
	\STATE \textbf{var} $s* \leftarrow 0$
	\FOR {$v$ $\in$ nodos, $v$ $\neq$ origen}
		\STATE Sacar a $v$ de su circuito
		\STATE \COMMENT Probar agregarlo entre cualquier par de nodos consecutivos
		\FOR {$w_{1}, w_{2} \in$ nodos, $w_{1}, w_{2}$ adyacentes en algún circuito con tamanio $>$ 4}
			\IF{$\neg$ es\_un\_movimiento\_tabu($w_{1}, w_{2}, v$)}
				\STATE $t \leftarrow$ $w$(agregar $v$ entre $w_{1}$ y  $w_{2}$)
				\IF{$t <$ $s*$ $~ \lor ~ s*$ == $0$}
					\STATE $s* \leftarrow t$
				\ENDIF
			\ENDIF
		\ENDFOR
		\STATE Volver a agregar a $v$ a su circuito
	\ENDFOR
	
	\STATE Modificar circuitos según $s*$
	\STATE $s*$ $\leftarrow$ nueva solución
	\IF {$w(s*) < w(s)$}
		\STATE \COMMENT Si es mejor que la que tenía, es mi nueva mejor solución y no la agrego a la lista tabú.
		\STATE $s \leftarrow s*$
	\ELSE
		\STATE \COMMENT Sino, agrego $s*$ a la lista tabú
		\IF{tamanio de \textit{listatabu} $==$ tabu\_size}
			\STATE \COMMENT Si se lleno la lista, popeo el primer elemento. Es decir, el más viejo.
			\STATE SacarPrimero de \textit{listatabú}
		\ENDIF		
		\STATE \COMMENT Agrego a la lista tabú la tupla que me dice que indica que ese movimiento es tabú
		\STATE AgregarAtrás de \textit{listatabú} a $< w_{1}, w_{2}, v,$ tamaño circuito1, tamaño circuito2 $>$
%		\STATE Agregar\_a\_lista\_tabu ($s*$)
	\ENDIF
	
\ENDWHILE

\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Líneas 1-2: Inicializaciones: $O(1)$
	\item \textit{While} 3-34: Se realiza $O(cant\_iteraciones)$.
		\begin{compactitem}
			\item Línea 4-5: Suma e inicialización: $O(1)$
			\item \textit{For} 7-19: Se realiza $O(n)$ veces.
				\begin{compactitem}
					\item Línea 8: Sacar elemento de la lista: $O(n)$
					\item \textit{For} 10-17: Se realiza $O(n)$ veces.
						\begin{compactitem}
							\item Línea 11: Chequear si es válido: $O(|listatabu|)$
							\item Línea 12: Calcular peso total, requiere recorrido lineal por todos los nodos: $O(n)$
							\item Líneas 13-14: Comparación y asignación: $O(1)$
						\end{compactitem}
					\item Línea 18: Agregar el nodo a la lista: $O(n)$
				\end{compactitem}
			\item Línea 20: Modificar circuitos (sacar y agregar un nodo de una lista): $O(n)$
			\item Línea 21: Asignación: $O(1)$
			\item Línea 22: Cálculo de pesos y comparación: $O(n)$.
			\item Línea 24: Copiar los circuitos: $O(n)$
			\item Líneas 27-32: Comparación ($O(1)$), Popear de una lista ($O(1)$), Agregar atrás ($O(1)$): $O(1)$.
		\end{compactitem}
	\item \textbf{\underline{Complejidad Total:}} Vamos a realizar $O(cantIteraciones)$ donde en cada iteración realizamos $O(n)$ iteraciones donde en cada una de esas iteraciones hace $O(n)$ iteraciones donde cada una cuesta $O(|listatabu| + n)$. Finalmente tenemos $O(cantIteraciones * n * n * (n+|listatabu|) = O(cantIteraciones * (n^{3} + n^{2} * |listatabu|))$.
		
%	\item \textit{For} 6-18: Es aplicar la misma idea que en búsqueda local: $O(n^{3})$
\end{compactitem}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operMA{es\_un\_movimiento\_tabu}{ \vin{$w_{1}$}{int}, \vin{$w_{2}$}{int}, \vin{$v$}{int}, \vin{$circ1$}{int}, \vin{$circ2$}{int}}}
%InstanceResultado inst, InstanceTP3 inst_pesos
\begin{algorithmic}[1]\parskip=1mm
\STATE \COMMENT Voy a recorrer la lista tabú
\FOR{ $l \in$ \textit{listatabu}}
		\IF{ primero de $l == w_{1} \land $ segundo de $l == w_{2} \land$ medio de $l == v \land $ tamaño circuito1 $== circ1 \land $ tamaño circuito2 $== circ2$ }
		\STATE \COMMENT Si quiero hacer un movimiento que ya está prohibido, devuelvo que lo es.
		\textbf{return} true
	\ENDIF
\ENDFOR
\STATE \textbf{return} false
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item \textit{For} 2-6: Recorrer la lista tabú y hacer 5 comparaciones: $O(|listatabu|)$
\end{compactitem}
\end{algorithm}

%\begin{algorithm}[H]
%\caption{\operMA{Agregar\_a\_lista\_tabu}{ \vin{$w_{1}$}{int}, \vin{$w_{2}$}{int}, \vin{$v$}{int}}}
%%InstanceResultado inst, InstanceTP3 inst_pesos
%\begin{algorithmic}[1]\parskip=1mm
%\STATE \COMMENT Voy a recorrer la lista tabú
%\FOR{ $l \in$ \textit{listatabu}}
%	\IF{ primero de $l == w_{1} \land $ segundo de $l == w_{2} \land$ medio de $l == v$ }
%		\STATE \COMMENT Si quiero hacer un movimiento que ya está prohibido, devuelvo que lo es.
%		\textbf{return} true
%	\ENDIF
%\ENDFOR
%\STATE \textbf{return} false
%\end{algorithmic}
%Complejidades:
%\begin{compactitem}
%	\item \textit{For} 2-6: Recorrer la lista tabú y hacer 3 comparaciones: $O(|listatabu|)$
%\end{compactitem}
%\end{algorithm}


\subsection{Complejidad (modelo uniforme)}

La complejidad de aplicar el algoritmo de tabú search es $O(cantIteraciones * (n^{3} + n^{2} * |listatabu|))$ que resulta, como se puede ver en el pseudocódigo, de aplicar % el constructor (que a su vez llama a diferentes funciones auxiliares) y obtener el resultado en $ O (1) $ con \textit{getRes}.
 la función \texttt{TabuSearch} (que a su vez llama a diferentes funciones auxiliares).

La complejidad está determinada por (en cada iteración) recorrer los $n$ nodos y para cada uno intentar ponerlo entre todos los pares consecutivos de nodos ($n$) (siempre y cuando sea válido, por esto tengo que recorrer la lista tabú ($O(|listatabu|)$)). Además, tiene que calcular el peso total para esa distribución en particular del nodo (lo que cuesta un barrido lineal de los nodos acumulando las distancias entre los nodos consecutivos ($O(n)$)). Luego nos queda $O(cantIteraciones * (n^{3} + n^{2} * |listatabu|))$.

Tanto la elección de la cantidad de iteraciones como el tamaño de la lista tabú me pueden modificar la complejidad. Si tienen un número constante, la complejidad será cúbica en la cantidad de nodos. Si, en cambio, se eligen valores en función de la cantidad de nodos, me puede variar la complejidad asintótica.

\subsection{Demostración de la solución}


El algoritmo de tabú search va a terminar ya que la cantidad de iteraciones que hace en cada uno de los ciclos depende únicamente del tamaño de los circuitos, los cuales son finitos, o de la cantidad de iteraciones que recibo como parámetro, la cual también es finita. Luego nunca puede pasar que itere infinitamente.

En cuanto a la solución, no tengo asegurado que sea la óptima. Lo que puedo asegurar es que, inicialmente, se van a realizar únicamente movimientos descendentes hasta llegar al mínimo local (aquí usamos el algoritmo de búsqueda local). Una vez que llegamos al mínimo, como no podemos avanzar decreciendo (sino no sería un mínimo local), hay que empeorar. Luego vamos a elegir el mejor de los vecinos y agregar el último movimiento que realizamos como prohibido sino existiría la posibilidad de volver a ese mínimo nuevamente e iterar entre estos dos movimientos hasta que se acaben las iteraciones. La lista tabú impide que pase eso, aunque, por un lado, el tamaño de la lista puede hacer que pase esto pero con ciclos ``más largos'', es decir, que no es infalible. Por otro lado, puede hacer que deseche soluciones ya que prohíbo hacer un movimiento y no tomo en cuenta cómo eran/son los circuitos cuando se prohibió/cuando quiero hacer el movimiento. Este es un riesgo que se asume ya que no se puede guardar la solución 
completa por un tema de memoria.

\newpage
\subsection{Tests}
%Para realizar las mediciones de los tests se usa una variable-contador insertada en el código, la cual va contando cada una de las operaciones básicas que se realizan a lo largo del algoritmo. Además se corrió por tiempo para verificar que los contadores cuentan correctamente.
%
%Además, ya que no encontramos casos patológicos para ninguno de los algoritmos, haremos los tests con un grafo con pesos random entre uno y 5000. Elegimos este número ya que llegamos a un acuerdo de que con los grafos con los que haríamos tests la diferencia en rendimiento y eficacia sería despreciable si los pesos eran mayores ya que no influencian de ninguna manera en la ejecución del algoritmo.
%
%\subsubsection{Test de Rendimiento}
%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/TestsFinales/TestRendTabu.png,width=0.9\linewidth,clip=}
%\caption{Tests de rendimiento de Tabú para grafos completos con distribución de pesos aleatorios. Longitud 20 de lista y 7 iteraciones como parámetros.}
%\end{figure}
%
%Nuestra complejidad teórica calculada era cúbica, pero nuestra empírica está acotada por n$^{5}$. No pudimos encontrar si el error está en la teórica o en el cálculo de la empírica.
%De nuevo, pudimos acotar el algoritmo por la complejidad esperada sin problemas.
% Por otro lado, como no existe ni un mejor ni un peor caso ya que siempre tiene que revisar todas las posibilidades para mover un nodo, decidimos simplemente mostrar el resultado con un grafo (el cual siempre tiene que ser completo) con distribución de pesos aleatorio. Dicho de otra manera, cualquier grafo que elijamos va a tardar lo mismo por lo que usamos uno con distribución de pesos aleatorio.

\subsubsection{Test de Resultados}
%De nuevo, decidimos testear la precisión del algoritmo recibiendo buenas y malas soluciones iniciales.
%
%\textit{Nota: para ver los resultados de la comparación entre éste y los demás algoritmos, referirse a la última sección del informe.}
%
%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/TestsFinales/TestSolTabu.png,width=0.9\linewidth,clip=}
%\caption{Análisis de resultados entre Tabú con diferentes soluciones iniciales. Longitud 20 de lista y 7 iteraciones como parámetros.}
%\end{figure}

%Aunque haya pasado algo muy parecido con el gráfico de la búsqueda local, no nos para de sorprender. La diferencia entre sumas mínimas de los grafos con soluciones buscadas por el Tabú con solución inicial mala tienen un crecimiento constante mientras que la de la \textbf{buena Tabú} tiene un crecimiento logarítmico o hasta se podría llegar a decir constante pero faltarían más pruebas para confirmar con seguridad.
%Similar a lo que sucedió en el test del algoritmo de Búsqueda Local, se puede ver que cuanto mayor es la cantidad de nodos, más se le complica mejorar la solución inicial mala. En este caso, a diferencia de aquel, el crecimiento de aplicar Tabú Search a la solución inicial mala es mucho más lento (esto se debe a que esta heurística es mejor que aquella). También el hecho de que sean constantes las longitudes de tamaño de lista y cantidad de iteraciones, hace que sea dispar la relación entre tener muchos o pocos nodos.
%
%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/testitertabu.png,width=0.9\linewidth,clip=}
%\caption{Análisis de resultados de Tabú para diferentes iteraciones. Tamaño de lista fijo en 10.}
%\end{figure}
%
%
%En este gráfico se puede ver cómo varía la solución cuando aumentamos la cantidad de iteraciones. Como era de esperarse, a medida que aumentan, la solución mejora. Esto se debe a que tiene más movimientos para hacer (y siempre que puede hacer un movimiento más, o mejora lo que tenía o se queda con eso. Nunca empeora en la solución final).
%
%
%
%
%
%La idea de este gráfico es ver, empíricamente, cuál es el tamaño de lista óptimo que uno debería elegir para aplicar esta metaheurística. Lo que hicimos fue correr para diferentes grafos de 50 nodos el algoritmo con distintas cantidades de tamaños listas y nos quedamos sólo con el mínimo tamaño que minimiza la suma de los pesos.
%
%Como se puede ver, esos valores quedan concentrados entre aproximadamente $n$ y $2*n$ (siendo n la cantidad de nodos, o sea, 50). Luego podemos decir que uno debería usar un tamaño de lista igual a $2*n$ para obtener, en general, el mejor resultado.=======
%En este gráfico se puede ver cómo varía la solución cuando aumentamos la cantidad de iteraciones. Como era de esperarse, a medida que aumentan, la solución mejora. Esto se debe a que tiene más movimientos para hacer (y siempre que puede hacer un movimiento más, o mejora lo que tenía o se queda con eso. Nunca empeora en la solución final).


Lo que quisimos mostrar en el siguiente gráfico es cómo se comporta en cada iteración el algoritmo para diferentes grafos de distintos tamaños. Como no encontramos ninguna familia de grafos que generen casos patológicos o interesantes, simplemente utilizamos grafos con distribución de pesos random.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-Tabu/ProgresoTabu.png,width=0.9\linewidth,clip=}
\caption{Análisis del progreso de tabú con 8 entradas distintas.}
\end{figure}

En primer lugar, se puede ver que en cada iteración se mejora la solución. A pesar de que yo puedo permitir realizar movimientos que me empeoren lo que tenía, la solución parcialmente final que obtuve hasta el momento nunca empeora.

Además, se puede ver que a diferencia de, por ejemplo, búsqueda local (en su sección está el test similar y usamos la misma escala para que se pueda apreciar lo que comentamos aquí), en este caso se realizan más iteraciones ya que no me quedo solo con el mínimo local sino que salgo de éste intentando llegar a otro mínimo local (con la esperanza de que sea el global, y sino volver a salir, etc). Por esto se puede ver que las soluciones son mucho mejores. Por ejemplo en el \textit{grafo 7}, pasa de 4300 a 3200.

%Además, se puede observar que la cantidad de iteraciones que le requiere al algoritmo llegar al mínimo (loca) puede variar mucho. Por ejemplo, en el \textit{grafo 1} tarda 5 iteraciones y en el \textit{grafo 8} tarda 25.

%Además, se puede apreciar que el mejoramiento de la solución final con respecto a la inicial, el cual varía mucho entre cada grafo. Esto tiene que ver con que si me dan una solución inicial que está muy cerca de un mínimo local que es mucho peor que el mínimo global, indefectiblemente yo voy a caer en ese ``pozo'' y no voy a poder acercarme nunca al global.

\subsubsection{Optimizar cantidad iteraciones Tabú y longitud de la lista}
Queríamos ver si se podía optimizar la cantidad de iteraciones pasadas como parámetro al Tabú. Es decir, obtener un valor mínimo tal que obtenga una solución relativamente buena. Lo mismo para la longitud de la lista.

Analicemos primero el test para ver si podemos optimizar cantidad de operaciones.

Para ello decidimos hacer dos tests. En el primero testeamos 90 grafos random pero todos con 50 nodos con una longitud fija de lista (2.4*n)  y variando la cantidad de iteraciones entre 1 y 500. Y como vamos variando las iteraciones de a 10, para cada grafo de los 90, analizamos el resultado de 50 iteraciones. En el segundo decidimos testear 30 grafos de 100 nodos cada uno con la misma idea de variación de cantidad de iteraciones.

Para el caso de optimizar la longitud de lista, hicimos algo similar. El primer test recibe la misma entrada (los 90 grafos) pero ahora fijamos la cantidad de iteraciones en 500 y vamos variando la longitud de lista entre 1 y 250, variando de a 10.


\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-Tabu/OptimizarIteraciones_50nodos.png,width=0.9\linewidth,clip=}
\caption{Histograma con el porcentaje de veces que una iteración fue la mejor con grafo de 50 nodos.}
\end{figure}


\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-Tabu/OptimizarIteraciones_100nodos.png,width=0.9\linewidth,clip=}
\caption{Histograma con el porcentaje de veces que una iteración fue la mejor con grafo de 100 nodos.}
\end{figure}



 
 
Como se puede ver en ambos gráficos, los valores están muy dispersos como para poder determinar fácilmente un rango que ``en general'' dé buenos resultados. De cualquier manera podemos establecer una cota de, por ejemplo, \textit{10*n}, para la que cualquier grafo estaría alcanzando su mínimo. Pero como esa cota para algunos tamaños implica un uso de tiempo impracticable, podemos usar un porcentaje menor y va a seguir dando bastantes buenos resultados ya que una gran parte de los grafos encuentran el mínimo en esos valores.

En todo caso, dado que ejecutar muchas iteraciones con \textit{n}s  muy grandes lleva demasiado tiempo, decidimos hacer el segundo test hasta 500 iteraciones, aunque sea n=100 y por ende la cantidad de iteraciones sea hasta 5*n; a diferencia del primero que iba hasta 10*n. Igual, en este test hay una predisposición de que el mínimo llegue en la iteración 71 del algoritmo, ya que en el gráfico se puede ver que es el número con mayor cantidad de mínimos. Sin embargo, faltarían probar más casos (hasta 1000 iteraciones por lo menos) para poder comparar completamente a ambos gráficos en la misma medida. Igual, se sigue aplicando que hay otros ``picos'' con iteraciones mayores y por ende, no es preferible hacer hasta 71 o un poco más de iteraciones pensando que se llega al mínimo con seguridad. Esto nos deja pensando que siempre mejora la eficacia del algoritmo mientras se aumente la cantidad de iteraciones, pero perdiendo rapidez y por ende se vuelva más lento.



\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-Tabu/OptimizarLongLista_50nodos.png,width=0.9\linewidth,clip=}
\caption{Histograma con el porcentaje de veces que una longitud de lista fue la mejor con grafo de 50 nodos.}
\end{figure}

En el caso de las listas pasa algo parecido en el sentido de que más implica mejor, pero es diferente en el sentido de que directamente no hay veces en las que el algoritmo llegó a un mínimo con una longitud chica: todos los casos en los que llegó son con longitud mayor a 61 y la gran mayoría con longitud mayor a 71. Esto nos deja pensando que es mucho mejor incrementar la longitud de lista, comparado con aumentar la cantidad de iteraciones en el anterior, ya que es mucho más probable mejorar la solución.


\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-Tabu/OptimizarLongLista_100nodos.png,width=0.9\linewidth,clip=}
\caption{Histograma con el porcentaje de veces que una longitud de lista fue la mejor con grafo de 100 nodos.}
\end{figure}

En este caso ocurre lo mismo que en el segundo caso de la optimización de iteraciones: deberíamos hacer con más longitudes de listas para que sea en las mismas condiciones (aumenta el n pero no aumenta el máximo de lista). Sin embargo, este gráfico sigue siendo interesante porque ahora sí aparecen casos en el que el mejor caso está entre las primeras longitudes de listas, específicamente la de longitud \texttt{1}. Aunque esto parezca extraño, puede pasar. Sería, probablemente, el caso en el que el mínimo local del principio es el mejor de todos, y por ende cuando intente salir con mayores longitudes de listas, no va a poder encontrar un mínimo mejor, aunque se vaya por otras soluciones. Entonces, aunque la suma total sea la misma para ambos tests con longitudes diferentes, sólo contaríamos la primera ya que estamos buscando la \textbf{mínima} longitud con la que llega al mínimo. Si hay dos longitudes distintas con las que llega al mínimo, nos quedamos con la menor por el tema de rapidez: menor implica más rápido.

